#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
#define endl '\n'

const int N = 2e5 + 10;
int pre1[N], pre0[N];

void solve() 
{
    int n; cin >> n;
    string s; cin >> s;
    int cnt1 = 0, cnt0 = 0;
    for(int i = 0; i < s.size(); i++)
        if(s[i] == '1') cnt1++;
        else cnt0++;
    LL k = (cnt1 - cnt0);
    double m = k * 1.0 / 2;
    LL p = 0;
    LL x = 0, len = 1e18;
    for(int i = 0; i < s.size() - 1; i++)
    {
        if(s[i] == '1') p++;
        else p--;
        if(abs(p - m) < len)
        {
            len = abs(p - m);
            x = p;
        }
    }

    cout << k * x - x * x << endl;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T;
	cin >> T;
	while(T--)
	{
        solve();
	}
	return 0;
}